/**
 * 
 */
package tree.passed2;

/**
 * @author xyyi
 *
 */
public class BinaryTreeMaximumPathSum {

	/**
	Given a binary tree, find the maximum path sum.

	The path may start and end at any node in the tree.

	For example:
	Given the below binary tree,

	   1
	  / \
	 2   3
	Return 6.
	 */
	public int maxPathSum(TreeNode root) {
		int[] max = new int[1];
		max[0] = Integer.MIN_VALUE;
		maxPathSumHelper(root, max);
		return max[0];
	}

	public int maxPathSumHelper(TreeNode root, int[] max) {

		// Base case 
		if (root == null) {
			return 0;
		}
		// Obtain left max and right max
		int leftMax = maxPathSumHelper(root.left, max);
		int rightMax = maxPathSumHelper(root.right, max);

		// Update global max
		int maxPath = root.val;
		maxPath = leftMax > 0 ? maxPath + leftMax : maxPath;
		maxPath = rightMax > 0 ? maxPath + rightMax : maxPath;
		max[0] = Math.max(max[0], maxPath);
		
		// pitfall only using leftMax or rightMax, if they are positive
		return leftMax > 0 || rightMax > 0 ? root.val
				+ Math.max(leftMax, rightMax) : root.val;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public BinaryTreeMaximumPathSum() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BinaryTreeMaximumPathSum btmps = new BinaryTreeMaximumPathSum();
		TreeNode root = btmps.new TreeNode(-3);
		int maxPath = btmps.maxPathSum(root);
		System.out.println(maxPath);
	}

}
